﻿/*  Groep 1:
*     János de Vries
*     Pelle Kersaan
*     Alex Aalbertsberg
*/ 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortOf
{
    public class RBTree<T> where T : IComparable
    {
        public RBNode<T> root;

        public RBTree()
        {
            root = null;
        }

        /// <summary>
        /// FAMILY DEFINITIONS
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public RBNode<T> Grandparent(RBNode<T> x)
        {
            return x.parent.parent;
        }

        public RBNode<T> Sibling(RBNode<T> x)
        {
            if (x == x.parent.left)
            {
                return x.parent.right;
            }
            else return x.parent.left;
        }

        public RBNode<T> Uncle(RBNode<T> x)
        {
            return Sibling(x.parent);
        }

        /// <summary>
        /// ROTATIONS
        /// </summary>
        /// <param name="node"></param>
        private void leftRotate(RBNode<T> node)
        {
            // rotates left around the given node.
            RBNode<T> r = node.right;
            ReplaceNode(node, r);
            node.right = r.left;
            if (r.left != null)
            {
                r.left.parent = node;
            }
            r.left = node;
            node.parent = r;
        }

        private void rightRotate(RBNode<T> node)
        {
            // rotates right around the given node.
            RBNode<T> l = node.left;
            ReplaceNode(node, l);
            node.left = l.right;
            if (l.right != null)
            {
                l.right.parent = node;
            }
            l.right = node;
            node.parent = l;
        }


        /// <summary>
        /// REPLACING
        /// </summary>
        /// <param name="node"></param>
        /// <param name="replaceNode"></param>
        public void ReplaceNode(RBNode<T> node, RBNode<T> replaceNode)
        {
            if (node.parent == null)
            {
                root = replaceNode;
            }
            else
            {
                if (node == node.parent.left)
                {
                    node.parent.left = replaceNode;
                }
                else
                {
                    node.parent.right = replaceNode;
                }
            }
            if (replaceNode != null)
            {
                replaceNode.parent = node.parent;
            }
        }

        /// <summary>
        /// INSERTION
        /// </summary>
        /// <param name="node"></param>

        public void InsertNode(RBNode<T> x)
        {
            if (root == null)
            {
                root = x;
            }
            else
            {
                RBNode<T> sentinel = root;
                while (true)
                {
                    int comparisonResult = x.data.CompareTo(sentinel.data);
                    if (comparisonResult < 0)
                    {
                        if (sentinel.left == null)
                        {
                            sentinel.left = x;
                            break;
                        }
                        else
                        {
                            sentinel = sentinel.left;
                        }
                    }
                    else
                    {
                        if (sentinel.right == null)
                        {
                            sentinel.right = x;
                            break;
                        }
                        else
                        {
                            sentinel = sentinel.right;
                        }
                    }
                }
                x.parent = sentinel;
            }
            InsertCase1(x);
        }

        /// <summary>
        /// INSERTION CASES
        /// </summary>
        /// <param name="x"></param>

        private void InsertCase1(RBNode<T> x)
        {
            // x is root
            if (x.parent == null)
            {
                x.color = "BLACK";
            }
            else
            {
                InsertCase2(x);
            }
        }

        private void InsertCase2(RBNode<T> x)
        {
            // x parent color is black
            if (x.parent.color == "BLACK")
            {
                return; // tree is valid
            }
            else
            {
                InsertCase3(x);
            }
        }

        private void InsertCase3(RBNode<T> x)
        {
            // x has an uncle and it's color is red
            if (Uncle(x) != null && Uncle(x).color == "RED")
            {
                // change colors of x's parent, x's uncle and x's grandparent
                x.parent.color = "BLACK";
                Uncle(x).color = "BLACK";
                Grandparent(x).color = "RED";
                // Apply case 1 for x's grandparent
                InsertCase1(Grandparent(x));
            }
            else
            {
                InsertCase4(x);
            }
        }

        private void InsertCase4(RBNode<T> x)
        {
            // if x is on the parent's right and the parent is on the grandparent's left
            if (x == x.parent.right && x.parent == Grandparent(x).left)
            {
                // rotate left around x's parent
                leftRotate(x.parent);
                x = x.left;
            }
            // if x is on the parent's left and the parent is on the grandparent's right
            else if (x == x.parent.left && x.parent == Grandparent(x).right)
            {
                // rotate right around x's parent
                rightRotate(x.parent);
                x = x.right;
            }
            InsertCase5(x);
        }

        private void InsertCase5(RBNode<T> x)
        {
            // set colors of x's parent and grandparent
            x.parent.color = "BLACK";
            Grandparent(x).color = "RED";
            // if x is on parent's left and parent is on grandparent's left
            if (x == x.parent.left && x.parent == Grandparent(x).left)
            {
                // rotate right around x's grandparent
                rightRotate(Grandparent(x));
            }
            else
            {
                // rotate left around x's grandparent
                leftRotate(Grandparent(x));
            }
        }

        /// <summary>
        /// Searches for the given node.
        /// </summary>
        /// <param name="node"></param>
        /// <returns>the node if it was found, and null if it was not found.</returns>
        public RBNode<T> Search(RBNode<T> node)
        {
            RBNode<T> sentinel = root;
            while (sentinel != null)
            {
                int comparisonResult = node.data.CompareTo(sentinel.data);
                if (comparisonResult == 0)
                {
                    return sentinel;
                }
                else if (comparisonResult < 0)
                {
                    sentinel = sentinel.left;
                }
                else
                {
                    sentinel = sentinel.right;
                }
            }
            return sentinel; // aka null at this point, as the node was not found.
        }

        /// <summary>
        /// Decides whether given node is a leaf (a leaf is a node without children).
        /// </summary>
        /// <param name="node"></param>
        /// <returns>true if given node is leaf, false if not.</returns>
        private Boolean is_leaf(RBNode<T> node)
        {
            return (node.left == null && node.right == null);
        }

        /// <summary>
        /// DELETION - NOT OPERATIONAL
        /// </summary>
        /// <param name="node"></param>

        public void Delete(RBNode<T> node)
        {
            RBNode<T> child;
            child = is_leaf(node.right) ? node.left : node.right;

            ReplaceNode(node, child);
            if (node.color == "BLACK")
            {
                if (child.color == "RED")
                {
                    child.color = "BLACK";
                }
                else
                {
                    DeleteCase1(node);
                }
            }
        }

        private void DeleteCase1(RBNode<T> node)
        {
            if (node.parent != null)
            {
                DeleteCase2(node);
            }
        }

        private void DeleteCase2(RBNode<T> node)
        {
            RBNode<T> s = Sibling(node);

            if (s.color == "RED")
            {
                node.parent.color = "RED";
                s.color = "BLACK";
                if (node == node.parent.left)
                {
                    leftRotate(node.parent);
                }
                else
                {
                    rightRotate(node.parent);
                }
            }
            DeleteCase3(node);
        }

        private void DeleteCase3(RBNode<T> node)
        {
            RBNode<T> s = Sibling(node);

            if ((node.parent.color == "BLACK") && (s.color == "BLACK") && (s.left.color == "BLACK") && (s.right.color == "BLACK"))
            {
                s.color = "RED";
                DeleteCase1(node.parent);
            }
            else
            {
                DeleteCase4(node);
            }
        }

        private void DeleteCase4(RBNode<T> node)
        {
            RBNode<T> s = Sibling(node);

            if ((node.parent.color == "RED") && (s.color == "BLACK") && (s.left.color == "BLACK") && (s.right.color == "BLACK"))
            {
                s.color = "RED";
                node.parent.color = "BLACK";
            }
            else
            {
                DeleteCase5(node);
            }
        }

        private void DeleteCase5(RBNode<T> node)
        {
            RBNode<T> s = Sibling(node);


            if (s.color == "BLACK")
            {
                if ((node == node.parent.left) && (s.right.color == "BLACK") && (s.left.color == "RED"))
                {
                    s.color = "RED";
                    s.left.color = "BLACK";
                    rightRotate(s);
                }
                else if ((node == node.parent.right) && (s.left.color == "BLACK") && (s.right.color == "RED"))
                {
                    s.color = "RED";
                    s.right.color = "BLACK";
                    leftRotate(s);
                }
            }
            DeleteCase6(node);
        }

        private void DeleteCase6(RBNode<T> node)
        {
            RBNode<T> s = Sibling(node);

            s.color = node.parent.color;
            node.parent.color = "BLACK";

            if (node == node.parent.left)
            {
                s.right.color = "BLACK";
                leftRotate(node.parent);
            }
            else
            {
                s.left.color = "BLACK";
                rightRotate(node.parent);
            }
        }



        /**
         * Initiates print method for this RBTree.
         */
        public void print()
        {
            String offset = "";
            printNode(root, ref offset);
            Console.WriteLine();
        }

        /**
         * Prints a separate node.
         */
        private void printNode(RBNode<T> node, ref String offset)
        {
            Console.WriteLine(offset + node.data.ToString());
            Console.WriteLine(offset + node.color.ToString());

            if (node.left != null && node.right != null)
            {
                Console.WriteLine(offset + "├─┐");
                offset += "│ ";
                printNode(node.right, ref offset);
                Console.WriteLine(offset);
                offset = offset.Substring(0, offset.Length - 2);
                printNode(node.left, ref offset);
            }
            else if (node.right != null)
            {
                Console.WriteLine(offset + "└─┐");
                offset += "  ";
                printNode(node.right, ref offset);
                offset = offset.Substring(0, offset.Length - 2);
            }
            else if (node.left != null)
            {
                Console.WriteLine(offset + "│");
                printNode(node.left, ref offset);
            }
        }

    }
}
